import java.util.PriorityQueue;

// 快速获得数据流的中位数的结构
// 测试链接 : https://leetcode.cn/problems/find-median-from-data-stream/
public class MedianFinderTest {

    class MedianFinder {

        /*
        思路把所有数分成一半，小的在大根堆，大的数在小根堆
         */
        public PriorityQueue<Integer> maxheap;  //大根堆
        public PriorityQueue<Integer> minheap;  //小根堆

        public MedianFinder() {
            maxheap = new PriorityQueue<>( (a,b)-> b-a );
            minheap = new PriorityQueue<>( (a,b)-> a-b );
        }

        public void addNum(int num) {
            if(maxheap.isEmpty()){   //首次加入
                maxheap.offer(num);
                return;
            }
            //大的 数放小根堆，小的数放大根堆
            if(num > maxheap.peek()) {
                minheap.offer(num);
            }else {
                maxheap.offer(num);
            }

            //调整两个堆的 数量
            if(maxheap.size() - minheap.size() > 1){  //大根堆比小根堆多两个
                minheap.offer(maxheap.poll());
            }
            if(minheap.size() - maxheap.size() > 1){
                maxheap.offer(minheap.poll());
            }

        }

        public double findMedian() {
            if(maxheap.size() == minheap.size()){
                return ( maxheap.peek() + minheap.peek() ) / 2.0;
            }
            if(maxheap.size() > minheap.size()){
                return maxheap.peek()*1.0;
            }else {
                return minheap.peek()*1.0;
            }

        }
    }
}
